#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e6+5;
const int MOD = 998244353;

int qpow(int a, int b){
    int res = 1;
    while(b){
        if ( b&1 ) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int fac[N], ifac[N];
void initfac(int n){ // n = N-1
    fac[0] = 1;
    for ( int i=1; i<=n; i++ )
        fac[i] = fac[i-1] * i % MOD;

    ifac[n] = qpow(fac[n], MOD-2); // fermat's littel theorem
    for ( int i=n; i>=1; i-- )
        ifac[i-1] = ifac[i] * i % MOD;
    
    assert(ifac[0] == 1);
}

int C( int n, int m ){
    if ( n<0 || m<0 || n<m ) return 0;
    return fac[n] * ifac[m] % MOD * ifac[n-m] % MOD;
}

int add(int a, int b){
    return (a+b) % MOD;
}

int mul(int a, int b){
    return a * b % MOD;
}

int norm(int a){
    return a % MOD;
}

int f[N];
int n,t;

signed main(){
    initfac(N-1);

    f[0] = 1;
    f[1] = 0;
    f[2] = f[3] = 1;
    for ( int i=4; i<=N-1; i++ ){
        f[i] = C(i-1, 1) * f[i-2] % MOD;
        f[i] += C(i-1, 2) * f[i-3] % MOD;
        f[i] = (f[i]) % MOD;
        f[i] += C(i-1, 3) * f[i-4] % MOD;
        f[i] = (f[i]) % MOD;

        assert(f[i] >= 0);
        if ( f[i] < 0 ){
            f[i] += MOD;
        }
    }

    cin >> t;
    while(t--){
        cin >> n;
        cout << f[n] << '\n';
    }
}